// https://www.lintcode.com/problem/look-for-points-that-are-bigger-than-the-surrounding-area/

public class Solution {
    /**
     * @param grid: a matrix
     * @return: Find all points that are strictly larger than their neighbors
     */
    public int[][] highpoints(int[][] grid) {
        // write your code here
        int rows = grid.length;
        int cols = grid[0].length;
        int[][] ret = new int[rows][cols];
        for (int i = 0; i < rows; ++i) {
          Arrays.fill(ret[i], -1);
        }
        for (int i = 0; i < rows; ++i) {
          for (int j = 0; j < cols; ++j) {
            if (ret[i][j] == -1) {
              if (checkAndMark(grid, ret, i, j, i - 1, j)) { // 上
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i + 1, j)) { // 下
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i, j - 1)) { // 左
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i, j + 1)) { // 右
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i - 1, j - 1)) { // 左上
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i + 1, j - 1)) { // 左下
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i - 1, j + 1)) { // 右上
                continue;
              }
              if (checkAndMark(grid, ret, i, j, i + 1, j + 1)) { // 右下
                continue;
              }
              ret[i][j] = 1;
            }
          }
        }
        return ret;
    }

    protected boolean checkAndMark(int[][] grid, int[][] ret, int i, int j, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;
        if ((r >= 0) && (r < rows) && (c >= 0) && (c < cols)) {
          if (grid[i][j] <= grid[r][c]) {
            ret[i][j] = 0;
            return true;
          }
        }
        return false;
    }
}